/*
 * @FilePath: \undefinedc:\Users\sxjct\.leetcode\912.排序数组.cpp
 * @Brief: 
 * @Version: 1.0
 * @Date: 2021-04-08 14:38:21
 * @Author: tianyiyi
 * @Copyright: Copyright@tianyiyi
 * @LastEditors: Mr.Tian
 * @LastEditTime: 2021-04-25 16:18:13
 */
/*
 * @lc app=leetcode.cn id=912 lang=cpp
 *
 * [912] 排序数组
 */

// @lc code=start
class Solution {
public:
    // /* 冒泡排序，超时，每一趟找到最大的元素，放在列表末尾 */
    // vector<int> sortArray(vector<int>& nums) {
    //     for(int i = 0;i < nums.size(); i++)
    //     {
    //         for(int j = 0; j < nums.size() - 1 - i; j++)
    //         {
    //             if(nums[j] > nums[j+1])
    //             {
    //                 int temp = nums[j];
    //                 nums[j] = nums[j+1];
    //                 nums[j + 1] = temp;
    //             }
    //         }
    //     }
    //     return nums;
    // }

    /* 选择排序，超时，每一趟找到最小的元素放在队首 */
    // vector<int> sortArray(vector<int>& nums)
    // {
    //     for(int i = 0;i < nums.size(); i++)
    //     {
    //         for(int j = i + 1;j <nums.size(); j++)
    //         {
    //             if(nums[i] > nums[j])
    //             {
    //                 int temp = nums[j];
    //                 nums[j] = nums[i];
    //                 nums[i] = temp;
    //             }
    //         }
    //     }
    //     return nums;
    // }

    /* 快排，分治思想 */
    // vector<int> sortArray(vector<int> &nums)
    // {
    //     quickSort(nums,0,nums.size() - 1);
    //     return nums;
    // }

    // void quickSort(vector<int> &nums,int left,int right)
    // {
    //     if(right >left)
    //     {
    //         int pivot = nums[left];             // 哨兵
    //         int low = left;
    //         int high = right;
    //         while (low < high)
    //         {
    //             while(nums[high] >= pivot && low < high)
    //             {
    //                 high--;
    //             }
    //             nums[low] = nums[high];
    //             while (nums[low] <= pivot && low < high)        
    //             {
    //                 low++;
    //             }
    //             nums[high] = nums[low];
    //         }
    //         nums[low] = pivot;
    //         quickSort(nums,left,low - 1);
    //         quickSort(nums,low+1,right);
    //     }
    // }







    vector<int> sortArray(vector<int> &nums)
    {
        quickSort(nums,0,nums.size() - 1);
        return nums;
    }


    void quickSort(vector<int> &nums,int left,int right)
    {
        if(left < right)
        {
            // 选择第一个元素作为哨兵
            int pivot = nums[left]; 

            // 
            int low = left;
            int high = right;
            while (low < high)
            {
                while(nums[high] >= pivot && low < high)
                {
                    high--;
                }
                nums[low] = nums[high];
                while(nums[low] <= pivot && low < high)
                {
                    low++;
                }
                nums[high] = nums[low];
            }
            nums[low] = pivot;
            quickSort(nums,left,low - 1);
            quickSort(nums,low + 1,right);
        }
    }

    void quickSort2(vector<int> &nums,int left,int right)
    {
        if(left < right)
        {
            int privt = nums[0];
            int low = left;
            int high = right;
            while(low < high)
            {
                while(privt <= nums[high] && low < high)
                {
                    high--;
                }
                nums[low] = nums[high];
                while(privt >= nums[low] && low < high)
                {
                    low++;
                }
                nums[high] = nums[low];
            }
            nums[low] = privt;
            quickSort2(nums,left,low - 1);
            quickSort2(nums,left + 1,high);
        }
    }


};
// @lc code=end

